9.8 束搜索

1.贪心搜索

在 9.7. 序列到序列学习（seq2seq）中我们在每个时间步，在经过 softmax 之后转化为概率，每次都选概率最大的那个词当做下一个词，这种方法是贪心搜索策略，但不能保证是全局最优的：
左边的贪心策略，选出的序列 ABC 不一定有右边非贪心的 ACB 好

2. 穷举搜索

假设我们要计算全部可能的序列，计算其概率，再选取概率最大的序列就是最好的序列，假设字典大小为 $n$，序列长度为 $T$，则要计算 $n^T$ 个序列

• $n=10000$，$T=10$，计算上不可行

束搜索

在贪心和穷举之间取个折中，每次保留 $k$ 个候选，复杂度指数变成乘法，在计算上是可行的：

k=2 的示意图，在每个时间步，考察 k*n 个序列概率最大的 k 个

• 时间复杂度 $O(knT)$

• 每个候选的最终分数是:

• 其中 $L$ 是序列长度，通常 $\alpha =0.75$，$k=5$ 或者 $10$